package sort_;

import java.util.Arrays;

/**
 * @author yicixingchen
 * @version 1.0
 * Create by 2022/10/27 16:10
 */

public class main {
    public static void main(String[] args) {
        selectionSort selectionSort = new selectionSort();
        selectionSort.sort(new int[]{6, 3, 8, 2, 9, 1, 19, 29, 5, 4});

        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.sort(new int[]{6, 3, 8, 2, 9, 1, 19, 29, 5, 4});

        insertSort insertSort = new insertSort();
        insertSort.sort(new int[]{6, 3, 8, 2, 9, 1, 19, 29, 5, 4});

        System.out.println("===========多态测试==============");

        polymorphism_ polymorphismTest = new polymorphism_();
        polymorphismTest.polymorphismTest(selectionSort, new int[]{6, 3, 8, 2, 9, 1, 19, 29, 5, 4});
        polymorphismTest.polymorphismTest(bubbleSort, new int[]{6, 3, 8, 2, 9, 1, 19, 29, 5, 4});
        polymorphismTest.polymorphismTest(insertSort, new int[]{6, 3, 8, 2, 9, 1, 19, 29, 5, 4});
    }
}

abstract class baseSort {
    public abstract void sort(int[] a);
}

class selectionSort extends baseSort {
    @Override
    public void sort(int[] a) {
        int count = 0;
        System.out.println("这是selectionSort");
        int min = 0;
        for (int i = 0; i <= a.length - 2; i++) {
            min = i;
            for (int j = i + 1; j <= a.length - 1; j++) {
                if (a[j] < a[min]) min = j;
                count++;
            }
            int t = a[i];
            a[i] = a[min];
            a[min] = t;
        }
        System.out.println(Arrays.toString(a) + "比较次数" + count);
    }
}

class BubbleSort extends baseSort {
    @Override
    public void sort(int[] a) {
        int count = 0;
        System.out.println("这是BubbleSort");
        for (int i = 0; i <= a.length - 2; i++) {
            for (int j = 0; j <= a.length - 2 - i; j++) {
                if (a[j + 1] < a[j]) {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
                }
                count++;
            }
        }
        System.out.println(Arrays.toString(a) + "比较次数" + count);
    }
}

class insertSort extends baseSort {
    @Override
    public void sort(int[] a) {
        System.out.println("这是insertSort");
        int count = 0;
        int v = 0;
        int j = 0;
        for (int i = 1; i <= a.length - 1; i++) {
            v = a[i];
            j = i - 1;
            count++;
            while (j >= 0 && a[j] > v) {
                a[j + 1] = a[j];
                j = j - 1;
                count++;
            }
            if((j>= 0)&&(a[j]<=v)) count++;
            a[j + 1] = v;
        }
        System.out.println(Arrays.toString(a) + "比较次数" + count);
    }
}

class polymorphism_ {
    void polymorphismTest(baseSort baseSort, int[] a) {
        baseSort.sort(a);
    }
}


